Image processing technology has become a key element in many systems such as robotic vision systems, satellite reconnaisance, OCR, visual inspection systems, and military weapons systems. Most image processing is now performed by digital algorithmic techniques on stored program computers. These techniques are so computationally intensive that, even with today's high-speed technology, many real time requirements can not be successfully met. In cases where there are no other alternatives, dedicated, highly parallel, special purpose digital techniques can be employed but the size and cost of such systems preclude their use in most applications. An important application of the present invention provides a high-speed, low cost, small size component which will provide good performance in practical image and pattern matching applications. Rapidly advancing, high performance analog semiconductor technology provides a viable alternative to digital processing techniques since high precision answers are not required in pattern matching applications. Usually the question to be answered is "which is the closest match in the finite ensemble of alternatives possible".
One specific embodiment of this invention provides a parallel hybrid analog-digital image processing device which will provide substantial improvement in image processing speeds (100 times) and implementation size and costs (10 times) over known digital techniques. The apparatus uses analog network techniques to calculate auto-correlation and cross-correlation functions in a highly parallel, hybrid analog-digital configuration.
The basic concept of the invention is generic in form and is amenable to many application-specific designs for different purposes, the Optical Character Recognition (OCR) application is only one. The inherent capability of the device to make a best match in the presence of inexact, incomplete or erroneous data opens many opportunities in decision-making situations in which the data cannot be expected to be perfect or complete. In the OCR application, input data is from a graphic source, but other data can be used from audio sources, radio frequency sources or a wide variety of other data categories.
Systems according to the invention lend themselves to translation of high level system concepts and functions directly into silicon designs. Because of the complexities and costs of large software based systems, as well as their inability to perform in real time, there is a trend toward more application-specific designs such as those provided by the present invention (which uses no software yet performs a very complex task); this direct system-to-silicon capability is very important in practical implementation of parallel computation techniques.
The device proposed may be classified as a member of the termed "connectionist" systems. Closely related to neural networks, the basic philosophy of a connectionist system is to provide the total knowledge base inherent in a system in a singular, simultaneous, and focused manner to the parallel input signal to be processed. The knowledge of a connectionist system is inherent in the device connections and weighting functions; the input image is applied directly and simultaneously to all elements of the system and directly controls the functions of those elements. The knowledge base of a digital system, in comparison, is contained in the software and the input signal must be stored in memory to await sequential (albeit somewhat parallel) processing by the software.
A system according to the invention is a hybrid which borrows from several related technology areas (parallel processing, neural networks, combined analog/digital functions, and connectionist systems) but does not exactly fit any of these. The distributed digital storage of cell weights in each cell relates to the parallel distributed memory concepts and also provides a convenient interface between the digital and analog worlds. The current summation techniques used internal to the cells and array of cells, the weighted inputs, and the firing of the highest charged correlation capacitor are closely related to neural network technology in its purest form, yet we do not consider essential the self-organizing or self-learning activities which are the center of the universe for the pure neural network technologists. Similarly, the knowledge of the system is based on interconnections and weights of the interconnections; hence the total knowledge base of the system is available simultaneously to interact with the total input image; these are characteristics of a connectionist system.
The elegant simplicity of devices according to the invention derives from combining the best techniques from the three associated areas in a unique fashion while avoiding the issues (primarily generality, universality, trainability, massive interconnection arrays, or exact modeling of human neurons) which have slowed progress in the respective fields and which are the subjects of most of the published literature. While theoretical research is desirable, the advantages of the invention lie in shorter term, application-specific techniques to solve current problems. The literature (See Appendix A hereinafter) provides a wealth of information in the three various areas discussed but does not reveal any activities, per se, into the type of system function and applications described here. None, for example, are specifically concerned about the speed, or bandwidth of their neural network circuit, they are typically modeled after human neurons and by design operate at about a 100 cycle per second rate; in accordance with the invention "neural" functions preferably occur at a 100,000 to 1,000,000 cycles per second rate. A brief summary of the traditional fields of parallel processing, neural networks, and connectionist systems and mainline efforts in each area is given below.
Research in parallel processing of interest is primarily directed at large arrays (&gt;10,000) of small, simple, stored program digital computing elements, some of which may be only one bit word length. The problems to be solved in this area of research are (1) the complexity of partitioning the problems in a balanced manner to fit the array processor characteristics; (2) software structuring to fit the problem/array processor structuring; and (3) inter-processor and inter-task communications. Typical of this area is the Connection machine, Reference (17). These types of digital architectures appear to be limited to specific classes of problems; they are now very application-limited and do not appear to be appropriate to broad classes of computing problems. The basic problem is that many of the difficult information processing problems are far too complex to readily be programmed by algorithmic means for multipurpose computers; additionally, total software experience is based on that approach and may not be appropriate for direct conversion to fit any general array or parallel processing characteristics. The situation may lead to a large number of problem-specific digital organizations typical of the present approach. The inadequacy of conventional computer systems for visual processing applications is documented in References (12), (13), (14), and (15).
Research in neural network technology is focused primarily in the areas of self-organization of large arrays of elements and in the techniques of iterative learning processes to reach optimum performance levels. Most research has been of such broad scope and so general that the difficulty of the problems studied distracts from the development of the elements themselves. An exception to this approach is the work of Hopfield and Tank, References (9)-(12), (18), who confine their scope to simpler problems, and are actively modeling analog neural networks for implementation in silicon form.
Their approach is to build an analog circuit described by the set of coupled non-linear differential equations they think describes the human neural network, so they are trying to duplicate as closely as possible the human brain equivalent. The question to be answered is whether the exact single neuron model is appropriate in small, microscopic applications such as we can put together compared to the real working environment of a human neuron, i.e. millions of neighbors and thousands of extremely complex interconnections, all of unknown significance at this time. In our understanding a related reservation as to "neural network" technology is whether the exact functional duplication is necessarily the best approach for important current problems, i.e. airplanes don't flap their wings to fly like birds do.
Hopfield and Tank have simulated and built, based on their model, a simple 4-bit analog to digital converter which converts analog inputs to digital codes. In addition, they have built a 900 element simulation model which solves the classic traveling salesman problem for a 30 city route. Settling time for this neural array was simulated to be 0.1 second. They calculated that to solve the same problem with conventional digital algorithms in the same 0.1 second would require about 10,000 times the amount of hardware required for their neural implementation. Fukushima, Reference (19), describes a numeric character recognition unit using multi-layer neural networks which derive features from the image; his predicted performance is roughly comparable to conventional techniques.
Several small scale neural networks of 20 to 30 neurons have been fabricated on a silicon die and demonstrate the basic practicality of IC implementation of hybrid analog-digital systems. See References (13), (18). These prior applications were primarily associative memory oriented in which an input word is applied to a group of stored words and the stored word which most closely resembles the input word is fetched from the memory without requiring physical addressing of the memory array.
The leading proponents of connectionist systems are the cognitive scientists who, in simulating complex behaviors of several hundred milli-seconds duration (representing about 100 processing cycles for neurons), have found that present day simulation programs require millions of steps to emulate those neural functions. There is a feeling that the digital computer as we know it today has, in effect, reached its limit for cognition problems. The Von Neumann computer, in essence, was designed to compute numbers and it is being realized now that this is not necessarily a good, or even a mediocre, solution in addressing higher level cognition and perception problems. Conventional computers were used in initial works because they were the tools most readily available. That use demonstrated the limitations of the stored program concept compared to the massively parallel or neural network functions being simulated and led to the connectionist movement. One fundamental premise of connectionism is that individual neurons do not transmit large amounts of symbolic information; instead, they compute by being appropriately connected to large numbers of similar units. See Feldman, Reference (2). The basic premise of stored program computers, on the other hand, is controlled data flows. The connectionist system requires very little data flow because of its other basic premise that all knowledge in the system is available simultaneously through its connections and weights. See Fahlman and Hinton, Reference (3). A distinction between the connectionist researcher and the neural network researcher is that the latter is more interested in the circuit level aspects while the former is more interested in using those circuits in a higher level system.
Another characteristic of current connectionist systems is that each identifiable object in the set has its own processing element. See Fahlman, ibid. This leads to a massive parallelism which ideally provides the characteristic that task execution time is time invariant. This means that the system can process 10, 100, 1,000, or more objects in the same fixed unit of time; the digital computer, on the other hand, would require linearly increasing periods of time. The penalty for this promising characteristic of a connectionist system is increasing hardware requirements with problem scope. However, if the connectionist computing element can be made small, as is possible in the present invention, then this penalty is not severe. The digital computer requires additional memory space for an expanded problem, as well. In fact, if the connectionist element could be made as small as a conventional memory cell, there would be no penalty relative to the digital computer. Generally the speed advantages far outweigh other considerations in the class of real time problems of concern.
In addition to providing the features and advantages described above, it is an object of the present invention to provide a template circuit for a hybrid digital-analog computer with parallel processing including a multiplicity of gate controlled current sources receiving digital signal bits and feeding a multiple input current summer thereby parallel summing a multiplicity of level-controlled analog signals in a simple, effective, and very rapid operation.
It is another object of the present invention to provide such apparatus wherein the current sources can be programmed to respond to either 0 or 1 input bits and also programmed to output different analog signal levels.
It is still another object of the present invention to provide such apparatus wherein a multiplicity of the above template circuits and their multiple current sources are also connected in parallel and comparators at the outputs of the summers detect and identify the template circuit with maximum response.
It is a further object of the present invention to provide an entire template circuit on a single IC chip having a self-adjusting gate voltage generator circuit to provide accurate analog computation in the face of uncertain circuit element parameter values.
It is yet another object of the present invention to provide correlation-determining apparatus as above-described wherein there is more than one stage of correlation with the output of the first stage providing inputs to the second stage.